package com.tony.study.PenTest;

import java.util.Deque;
import java.util.LinkedList;

/**
 * Created with IntelliJ IDEA.
 *
 * @Title: EvalRPN
 * @Auther: 皮蛋布丁
 * @Date: 2021/11/03/10:41
 * @Description: 逆波兰表达式(栈/数组模拟栈)
 */
public class EvalRPN {

    public static void main(String[] args) {
        String[] tokens = new String[] {"2","1","+","3","*"};
        String[] tokens1 = new String[] {"4","13","5","/","+"};
        System.out.println(evalRPN(tokens));
        System.out.println(evalRPN(tokens1));

        System.out.println(evalRPN1(tokens));
        System.out.println(evalRPN1(tokens1));
    }

    /**
    * @Description: evalRPN 通过栈实现
    * @Param: [tokens]
    * @return: int
    * @Author: 皮蛋布丁
    * @Date: 2021/11/3 13:17
    */
    public static int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<Integer>();
        int n = tokens.length;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            if(isNumber(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                int num2 = stack.pop();
                int num1 = stack.pop();
                switch (token) {
                    case "+":
                        stack.push(num1 + num2);
                        break;
                    case "-":
                        stack.push(num1 - num2);
                        break;
                    case "*":
                        stack.push(num1 * num2);
                        break;
                    case "/":
                        stack.push(num1 / num2);
                        break;
                    default:
                }
            }
        }
        return stack.pop();
    }
    public static boolean isNumber(String toekn) {
        return !("+".equals(toekn) || "-".equals(toekn) || "*".equals(toekn) || "/".equals(toekn));
    }

    /**
    * @Description: evalRPN1 数组模拟栈实现(长度n一定是奇数，且操作数的个数一定比运算符的个数多1个)
    * @Param: [tokens]
    * @return: int
    * @Author: 皮蛋布丁
    * @Date: 2021/11/3 13:18
    */
    public static int evalRPN1(String[] tokens) {
        int n = tokens.length;
        int[] stack = new int[(n + 1) / 2];
        int index = -1;
        for (int i = 0; i < n; i++) {
            String token = tokens[i];
            switch (token) {
                case "+":
                    index--;
                    stack[index] += stack[index + 1];
                    break;
                case "-":
                    index--;
                    stack[index] -= stack[index + 1];
                    break;
                case "*":
                    index--;
                    stack[index] *= stack[index + 1];
                    break;
                case "/":
                    index--;
                    stack[index] /= stack[index + 1];
                    break;
                default:
                    index++;
                    stack[index] = Integer.parseInt(token);
            }
        }
        return stack[index];
    }

}
